Least and Greatest Solutions of Equations over Sets of Integers
Identifieur interne : 003059 ( Main/Exploration ); précédent : 003058; suivant : 003060Least and Greatest Solutions of Equations over Sets of Integers
Auteurs : Artur Je [Pologne] ; Alexander Okhotin [Finlande]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, $S+T=\{m+n \mid m \in S, \: n \in T\}$ . These equations were recently studied by the authors (“On equations over sets of integers”, STACS 2010), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the $\Sigma^1_1$ sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved form X i = ϕ i (X 1, ..., X n ). Least solutions of such resolved systems represent exactly the recursively enumerable sets.
Url:
DOI: 10.1007/978-3-642-15155-2_39
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002A99
- to stream Istex, to step Curation: 002A62
- to stream Istex, to step Checkpoint: 000821
- to stream Main, to step Merge: 003116
- to stream Main, to step Curation: 003059
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Least and Greatest Solutions of Equations over Sets of Integers</title><author><name sortKey="Je, Artur" sort="Je, Artur" uniqKey="Je A" first="Artur" last="Je">Artur Je</name></author><author><name sortKey="Okhotin, Alexander" sort="Okhotin, Alexander" uniqKey="Okhotin A" first="Alexander" last="Okhotin">Alexander Okhotin</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:B5C5C80D81761768A7C4D4833FCDBB1F3440BE71</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-15155-2_39</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-25950C8D-2/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002A99</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002A99</idno><idno type="wicri:Area/Istex/Curation">002A62</idno><idno type="wicri:Area/Istex/Checkpoint">000821</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000821</idno><idno type="wicri:doubleKey">0302-9743:2010:Je A:least:and:greatest</idno><idno type="wicri:Area/Main/Merge">003116</idno><idno type="wicri:Area/Main/Curation">003059</idno><idno type="wicri:Area/Main/Exploration">003059</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Least and Greatest Solutions of Equations over Sets of Integers</title><author><name sortKey="Je, Artur" sort="Je, Artur" uniqKey="Je A" first="Artur" last="Je">Artur Je</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Institute of Computer Science, University of Wrocław</wicri:regionArea><wicri:noRegion>University of Wrocław</wicri:noRegion></affiliation></author><author><name sortKey="Okhotin, Alexander" sort="Okhotin, Alexander" uniqKey="Okhotin A" first="Alexander" last="Okhotin">Alexander Okhotin</name><affiliation wicri:level="4"><country xml:lang="fr">Finlande</country><wicri:regionArea>Department of Mathematics, University of Turku</wicri:regionArea><placeName><settlement type="city">Turku</settlement><region type="région" nuts="2">Finlande occidentale</region></placeName><orgName type="university">Université de Turku</orgName></affiliation><affiliation></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Finlande</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, $S+T=\{m+n \mid m \in S, \: n \in T\}$ . These equations were recently studied by the authors (“On equations over sets of integers”, STACS 2010), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the $\Sigma^1_1$ sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved form X i = ϕ i (X 1, ..., X n ). Least solutions of such resolved systems represent exactly the recursively enumerable sets.</div></front></TEI><affiliations><list><country><li>Finlande</li><li>Pologne</li></country><region><li>Finlande occidentale</li></region><settlement><li>Turku</li></settlement><orgName><li>Université de Turku</li></orgName></list><tree><country name="Pologne"><noRegion><name sortKey="Je, Artur" sort="Je, Artur" uniqKey="Je A" first="Artur" last="Je">Artur Je</name></noRegion></country><country name="Finlande"><region name="Finlande occidentale"><name sortKey="Okhotin, Alexander" sort="Okhotin, Alexander" uniqKey="Okhotin A" first="Alexander" last="Okhotin">Alexander Okhotin</name></region><name sortKey="Okhotin, Alexander" sort="Okhotin, Alexander" uniqKey="Okhotin A" first="Alexander" last="Okhotin">Alexander Okhotin</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003059 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003059 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:B5C5C80D81761768A7C4D4833FCDBB1F3440BE71
|texte= Least and Greatest Solutions of Equations over Sets of Integers
}}
| This area was generated with Dilib version V0.6.33. |  |